package 代码随想录_回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zx
 * @create 2022-06-08 15:23
 * ##########################二刷的时候把关于去重是树层去重还是树枝去重标注一下#####################################
 * 回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案
 * 组合无序，排列有序
 * 回溯法解决的问题都可以抽象为树形结构,指的是所有回溯法的问题都可以抽象为树形结构
 * 集合的大小就构成了树的宽度,递归的深度,都构成的树的深度.
 * 回溯法抽象为树形结构后,其遍历过程就是：【for循环横向遍历,递归纵向遍历,回溯不断调整结果集】
 *
 * 强调一下,回溯法中递归函数参数很难一次性确定下来,一般先写逻辑,需要啥参数了,填什么参数.
 *
 * 回溯三部曲:
 * 回溯函数模板返回值以及参数
 * 回溯函数终止条件
 * 回溯搜索的遍历过程
 *
 * 如果是一个集合来求组合的话,就需要startIndex,例如：77.组合，216.组合总和III.
 * 如果是多个集合取组合,各个集合之间相互不影响,那么就不用startIndex,例如：17.电话号码的字母组合
 * 无序,取过的元素不会重复取,写回溯算法的时候,for就要从startIndex开始,而不是从0开始！
 * 求取子集问题,不需要任何剪枝！因为子集就是要遍历整棵树.
 *
 * 理解"树层去重"和"树枝去重"非常重要.(去重需要先对集合排序)
 * 元素在同一个组合内是可以重复的,怎么重复都没事,但两个组合不能相同.
 * 所以要去重的是同一树层上的“使用过”,同一树枝上的都是一个组合里的元素,不用去重.
 * 强调一下，树层去重的话，需要对数组排序！！！！！！！！！！！！！！！！(40、47、90-leetcode)！！！！！
 *
 * 排列是有序的,也就是说[1,2] 和[2,1]是两个集合,这和之前的子集以及组合所不同的地方。
 * 元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不使用startIndex
 * 排列问题需要一个used数组,标记已经选择的元素
 *
 * 排列问题的不同：
 * 每层都是从0开始搜索而不是startIndex
 * 需要used数组记录path里都放了哪些元素了
 *
 * 一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果,而子集问题就是取树上所有节点的结果.
 * 如果要对树层中前一位去重,就用used[i - 1] == false,如果要对树枝前一位去重用used[i - 1] == true
 * 对于排列问题,树层上去重和树枝上去重,都是可以的,但是树层上去重效率更高！
 *
 * 归纳总结(代码随想录里的总结真的牛逼！！！！)：
 * 回溯算法：递增子序列的去重是同一个父节点下的本层的去重。
 * 回溯算法：求子集问题(二)的去重是要整颗树的本层去重,但是整棵树的同一层去重不好操作,所以才排序,与前一个树枝对比就可以了.
 * 理解以上内容，就知道了：
 * 回溯算法：递增子序列去重用set的定义为什么放在单层搜索的逻辑里,而不是放在全局变量里.。
 *
 * 子集是收集树形结构中树的所有节点的结果。而组合问题、分割问题是收集树形结构中叶子节点的结果
 *
 *
 * 1. 排列问题需要用到used数组！！！
 *
 * 2. startIndex <---> i + 1：每个数字最多使用一次
 *
 *
 * 3. 控制结果集去重(去重需要排序)：
 *   Arrays.sort(~);
     if(i > startIndex && candidates[i] == candidates[i - 1]){
         continue;
     }
 */
public class Test {

}
